package 找到字符串中所有字母异位词;

import java.util.ArrayList;
import java.util.List;
class Solution {
    //解法一:用循环判断
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int n = p.length();
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            hash[p.charAt(i) - 97]++;
        }
        int left = 0;
        int right = 0;
        int[] hash2 = new int[26];
        while (right < s.length()){
            hash2[s.charAt(right) - 97]++;
            if (right - left + 1 == n){
                boolean flg = true;
                for (int i = 0; i < hash.length; i++) {
                    if(hash[i] != hash2[i]){
                        flg = false;
                        break;
                    }
                }
                if (flg){
                    ret.add(left);
                }
                hash2[s.charAt(left) - 97]--;
                left++;
            }
            right++;
        }
        return ret;
    }
    //解法二:用变量 count 来判断
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int m = p.length();
        char[] str1 = p.toCharArray();
        int[] hash1 = new int[26];
        for(int i = 0; i < m; i++){
            hash1[str1[i] - 'a']++;
        }
        int len = s.length();
        int[] hash2 = new int[26];
        char[] str2 = s.toCharArray();
        for(int left = 0,right = 0,count = 0; right < len; right++){
            if(++hash2[str2[right] - 'a'] <= hash1[str2[right] - 'a']){
                count++;
            }
            if(right - left + 1 > m){
                if(--hash2[str2[left] - 'a'] < hash1[str2[left++] - 'a']){
                    count--;
                }
            }
            if(count == m){
                ret.add(left);
            }
        }
        return ret;
    }
}